package com.lft.tree15.rbtree;

import java.util.Scanner;

/**
 * @author Laifengting
 */
public class RedBlackTreeDemo {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		RedBlackTree<String, Object> redBlackTree = new RedBlackTree<>();
		while (true) {
			System.out.println("请输入Key: ");
			String key = scanner.next();
			System.out.println();
			redBlackTree.insert(key, null);
			TreeOperation.show(redBlackTree.getRootNode());
		}
	}
}

class RedBlackTree<K extends Comparable<K>, V> {
	/**
	 * ① 创建RedBlackTree，定义颜色
	 */
	private static final boolean RED = true;
	private static final boolean BLACK = false;
	
	/**
	 * 根节点
	 */
	private RedBlackNode rootNode;
	
	/**
	 * 获取根节点
	 * @return
	 */
	public RedBlackNode getRootNode() {
		return rootNode;
	}
	
	// ③ 辅助方法定义：parentOf(node),isRed(node),isBlack(node),setRed(node),setBlack(node),inOrderPrint()
	
	/**
	 * 获取当前节点的父节点
	 * @param node
	 * @return RedBlackNode 当前节点的父节点
	 */
	private RedBlackNode parentOf(RedBlackNode node) {
		if (node != null) {
			return node.getParent();
		}
		return null;
	}
	
	/**
	 * 判断当前节点是否是红色
	 * @param node
	 */
	private boolean isRed(RedBlackNode node) {
		if (node != null) {
			return node.isColor() == RED;
		}
		return false;
	}
	
	/**
	 * 判断当前节点是否是黑色
	 * @param node
	 */
	private boolean isBlack(RedBlackNode node) {
		if (node != null) {
			return node.isColor() == BLACK;
		}
		return false;
	}
	
	/**
	 * 将节点设置为红色
	 * @param node
	 */
	private void setRed(RedBlackNode node) {
		if (node != null) {
			node.setColor(RED);
		}
	}
	
	/**
	 * 将节点设置为黑色
	 * @param node
	 */
	private void setBlack(RedBlackNode node) {
		if (node != null) {
			node.setColor(BLACK);
		}
	}
	
	/**
	 * 中序打印二叉树
	 */
	public void infixOrderPrint() {
		infixOrderPrint(this.rootNode);
	}
	
	/**
	 * 私有中序遍历方法
	 * @param node 要遍历的根节点
	 */
	private void infixOrderPrint(RedBlackNode node) {
		if (node != null) {
			infixOrderPrint(node.left);
			System.out.println("key:" + node.getKey() + " value:" + node.getValue());
			infixOrderPrint(node.right);
		}
	}
	
	// ④ 左旋方法定义：leftRotate(node)
	
	/**
	 * 左旋方法
	 * 左旋示意图：左旋x节点
	 * //       p                   p
	 * //       |                   |
	 * //       x                   y
	 * //      / \      ---->      / \
	 * //    lx  y               x   ry
	 * //       / \             / \
	 * //      ly  ry          lx  ly
	 * 1.并将 x 的右子节点指向 y 的左子节点(ly),将 y 的左子节点的父节点更新为 x
	 * 2.当x的父节点(不为空时)，更新y的父节点为x的父节点，并将x原父节点的子树指向y
	 * 3.将x的父节点更新为y，将y的左子节点更新为x
	 * @param xNode 需要操作左旋的节点
	 */
	private void leftRotate(RedBlackNode xNode) {
		if (xNode != null) {
			RedBlackNode yNode = xNode.getRight();
			// 1.1并将x的右子节点指向 y 的左子节点(ly)
			xNode.setRight(yNode.getLeft());
			// 1.2将y的左子节点的父节点更新为x
			if (yNode.getLeft() != null) {
				yNode.getLeft().setParent(xNode);
			}
			// 2.当x的父节点(不为空时)，更新y的父节点为x的父节点，并将x原父节点的子树指向y
			if (xNode.getParent() != null) {
				yNode.setParent(xNode.getParent());
				if (xNode == xNode.getParent().getLeft()) {
					xNode.getParent().setLeft(yNode);
				} else {
					xNode.getParent().setRight(yNode);
				}
			} else {
				// x为根节点时，需要更新y为根节点
				this.rootNode = yNode;
				this.rootNode.setParent(null);
			}
			// 3.将x的父节点更新为y，将y的左子节点更新为x
			xNode.setParent(yNode);
			yNode.setLeft(xNode);
		}
	}
	
	// ⑤ 右旋方法定义：rightRotate(node)
	
	/**
	 * 右旋方法
	 * 右旋示意图：右旋y节点
	 * //     p                       p
	 * //     |                       |
	 * //     y                       x
	 * //    / \          ---->      / \
	 * //   x   ry                  lx  y
	 * //  / \                         / \
	 * // lx  ly                      ly  ry
	 * 1. 将 y 的左子节点指向 x 的右子节点，并且更新 x 的右子节点的父节点为 y
	 * 2. 当 y 的父节点不为空时，更新 x 的父节点为 y 的父节点，更新 y 的父节点的指定子节点（y当前的位置）为 x
	 * 3. 更新 y 的父节点为 x，更新 x 的右子节点为 y
	 * @param yNode 需要操作右旋的节点
	 */
	private void rightRotate(RedBlackNode yNode) {
		if (yNode != null) {
			RedBlackNode xNode = yNode.getLeft();
			// 1.1将y的左子节点指向 x 的右子节点(ly)
			yNode.setLeft(xNode.getRight());
			// 1.2将x的右子节点的父节点更新为y
			if (xNode.getRight() != null) {
				xNode.getRight().setParent(yNode);
			}
			// 2.当y的父节点(不为空时)，更新x的父节点为y的父节点，更新 y 的父节点的指定子节点（y当前的位置）为 x
			if (yNode.getParent() != null) {
				xNode.setParent(yNode.getParent());
				if (yNode == yNode.getParent().getLeft()) {
					yNode.getParent().setLeft(xNode);
				} else {
					yNode.getParent().setRight(xNode);
				}
			} else {
				// y为根节点时，需要更新x为根节点
				this.rootNode = xNode;
				this.rootNode.setParent(null);
			}
			// 3.将y的父节点更新为x，将x的右子节点更新为y
			yNode.setParent(xNode);
			xNode.setRight(yNode);
		}
	}
	
	// ⑥ 公开插入接口方法定义：insert(K key,V value)
	// ⑦ 私有插入接口方法定义：insert(RedBlackNode node)
	
	/**
	 * 公开的插入方法
	 * @param key
	 * @param value
	 */
	public void insert(K key, V value) {
		RedBlackNode node = new RedBlackNode();
		node.setKey(key);
		node.setValue(value);
		// 新节点一定是红色！！
		node.setColor(RED);
		insert(node);
	}
	
	/**
	 * 插入 节点
	 * @param node
	 */
	private void insert(RedBlackNode node) {
		// 第一步：查找当前node的父节点
		RedBlackNode parent = null;
		RedBlackNode x = this.rootNode;
		
		while (x != null) {
			parent = x;
			// 按字符串对比，cmp > 0，说明 node.key 大于 x.key，需要到 x 的右子树查找。
			// cmp == 0,说明 node.key 等于 x.key，需要进行替换。
			// cmp < 0,说明 node.key 小于 x.key，需要要 x 的左子树查找。
			int cmp = node.getKey().compareTo(x.getKey());
			if (cmp > 0) {
				x = x.getRight();
			} else if (cmp == 0) {
				x.setValue(node.getValue());
				return;
			} else {
				x = x.getLeft();
			}
		}
		node.setParent(parent);
		if (parent != null) {
			// 判断 node 与 parent 的key谁大。
			int cmp = node.getKey().compareTo(parent.getKey());
			if (cmp > 0) {
				// 当前 node 的 key 比 parent 的大。需要把 node 放入 parent 的右子节点
				parent.setRight(node);
			} else {
				// 当前 node 的 key 比 parent 的小。需要把 node 放入 parent 的左子节点
				parent.setLeft(node);
			}
		} else {
			// 如果 parent 为空，说明直接插入的节点就是根节点。
			this.rootNode = node;
		}
		
		// 需要调用修复红黑树平衡的方法
		insertFixUp(node);
	}
	// ⑧ 修改插入导致红黑树失衡的方法定义：insertFixUp(RedBlackNode node)
	
	/**
	 * 插入后修复红黑树平衡的方法
	 * //    |---情景1：红黑树为空树，将根节点变色为黑色。
	 * //    |---情景2：插入节点的key已经存在，不需要平衡。
	 * //    |---情景3：插入节点的父节点为黑色，不需要平衡。
	 * //    情景4 需要咱们去处理
	 * //    |---情景4：插入节点的父节点为红色
	 * //         |---情景4.1：叔叔节点存在，并且为红色（父-叔 双红），将叔父节点都染色为黑色，将祖父节点染色为红色。并且再以祖父节点为当前节点，再进行下一步处理。
	 * //         |---情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
	 * //              |---情景4.2.1：插入节点为其父节点的左子节点（LL情况），将父节点染色为黑色，祖父节点染色为红色，以祖父节点为当前节点，进行右旋。
	 * //              |---情景4.2.2：插入节点为其父节点的右子节点（LR情况），先以父节点为当前节点，进行左旋。得到LL双红，再进行变色，右旋。
	 * //         |---情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
	 * //              |---情景4.3.1：插入节点为其父节点的右子节点（RR情况），将父节点染色为黑色，祖父节点染色为红色，以祖父节点为当前节点，进行左旋。
	 * //              |---情景4.3.2：插入节点为其父节点的左子节点（RL情况），先以父节点为当前节点，进行右旋。得到RR双红，再进行变色，左旋。
	 */
	private void insertFixUp(RedBlackNode node) {
		this.rootNode.setColor(BLACK);
		// 临时引用，父节点
		RedBlackNode parent = parentOf(node);
		// 临时引用，祖父节点
		RedBlackNode gParent = parentOf(parent);
		// 情景4：插入节点的父节点为红色
		if (parent != null && isRed(parent)) {
			// 如果父节点是红色，那么一定存在祖父节点。因为根节点不能是红色。
			
			// 临时引用，叔节点
			RedBlackNode uncle = null;
			// 父节点是祖父节点的左子节点。
			if (parent == gParent.getLeft()) {
				// 叔节点就是祖父节点的右子节点。
				uncle = gParent.getRight();
				
				// 情景4.1：叔节点存在，并且为红色（父-叔 双红），
				if (uncle != null && isRed(uncle)) {
					// 将叔父节点都染色为黑色，将祖父节点染色为红色。并且再以祖父节点为当前节点，再进行下一步处理。
					setBlack(parent);
					setBlack(uncle);
					setRed(gParent);
					insertFixUp(gParent);
					return;
				}
				
				// 情景4.2：叔叔节点不存在，或者为黑色
				if (uncle == null || isBlack(uncle)) {
					// 情景4.2.1：插入节点为其父节点的左子节点（LL情况），将父节点染色为黑色，祖父节点染色为红色，以祖父节点为当前节点，进行右旋。
					if (node == parent.getLeft()) {
						parent.setColor(BLACK);
						gParent.setColor(RED);
						rightRotate(gParent);
						return;
					}
					// 情景4.2.2：插入节点为其父节点的右子节点（LR情况），先以父节点为当前节点，进行左旋。得到LL双红，然后指定父节点为当前节点进行下一轮处理。
					if (node == parent.getRight()) {
						leftRotate(parent);
						insertFixUp(parent);
						return;
					}
				}
				
			}
			// 父节点是祖父节点的右子节点。
			if (parent == gParent.getRight()) {
				// 叔节点就是祖父节点的左子节点。
				uncle = gParent.getLeft();
				
				if (uncle != null && isRed(uncle)) {
					// 将叔父节点都染色为黑色，将祖父节点染色为红色。并且再以祖父节点为当前节点，再进行下一步处理。
					setBlack(parent);
					setBlack(uncle);
					setRed(gParent);
					insertFixUp(gParent);
					return;
				}
				
				// 情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
				if (uncle == null || isBlack(uncle)) {
					//情景4.3.1：插入节点为其父节点的右子节点（RR情况），将父节点染色为黑色，祖父节点染色为红色，以祖父节点为当前节点，进行左旋。
					if (node == parent.getRight()) {
						parent.setColor(BLACK);
						gParent.setColor(RED);
						leftRotate(gParent);
						return;
					}
					
					// 情景4.3.2：插入节点为其父节点的左子节点（RL情况），先以父节点为当前节点，进行右旋。得到RR双红，再以父节点为当前节点，进行下一步处理。。
					if (node == parent.getLeft()) {
						rightRotate(parent);
						insertFixUp(parent);
						return;
					}
				}
				
			}
			
		}
	}
	
	/**
	 * 静态内部类——红黑节点类
	 * ② 创建RedBlackNode
	 */
	static class RedBlackNode<K extends Comparable<K>, V> {
		/**
		 * 父节点
		 */
		private RedBlackNode parent;
		/**
		 * 左子节点
		 */
		private RedBlackNode left;
		/**
		 * 右子节点
		 */
		private RedBlackNode right;
		/**
		 * 颜色，true表示红色，false表示黑色。
		 */
		private boolean color;
		
		/**
		 * 键
		 */
		private K key;
		/**
		 * 值
		 */
		private V value;
		
		public RedBlackNode() {
		}
		
		public RedBlackNode(RedBlackNode parent, RedBlackNode left, RedBlackNode right, boolean color, K key, V value) {
			this.parent = parent;
			this.left = left;
			this.right = right;
			this.color = color;
			this.key = key;
			this.value = value;
		}
		
		/**
		 * 获取父节点
		 * @return
		 */
		public RedBlackNode getParent() {
			return parent;
		}
		
		/**
		 * 设置父节点
		 * @param parent
		 */
		public void setParent(RedBlackNode parent) {
			this.parent = parent;
		}
		
		/**
		 * 获取左子节点
		 * @return
		 */
		public RedBlackNode getLeft() {
			return left;
		}
		
		/**
		 * 设置左子节点
		 * @param left
		 */
		public void setLeft(RedBlackNode left) {
			this.left = left;
		}
		
		/**
		 * 获取右子节点
		 * @return
		 */
		public RedBlackNode getRight() {
			return right;
		}
		
		/**
		 * 设置右子节点
		 * @param right
		 */
		public void setRight(RedBlackNode right) {
			this.right = right;
		}
		
		/**
		 * 返回颜色
		 * @return true红色，false黑色
		 */
		public boolean isColor() {
			return color;
		}
		
		/**
		 * 设置颜色。
		 * @param color true红色，false黑色
		 */
		public void setColor(boolean color) {
			this.color = color;
		}
		
		public K getKey() {
			return key;
		}
		
		public void setKey(K key) {
			this.key = key;
		}
		
		public V getValue() {
			return value;
		}
		
		public void setValue(V value) {
			this.value = value;
		}
	}
}